The present invention relates to a method and apparatus for controlling a storage device and, more particularly, to a method and apparatus for controlling a write processing operation when a plurality of processors generate write requests in parallel.
In communication system such as ATM (Asynchronous Transfer Mode) or the like, a plurality of data processing means such as processors perform various processing operations using external or internal storage units.
In these systems, it is important to keep track of data among a plurality of storage units with contents related to each other when the plurality of processors issue requests in parallel for write processing in the storage units. In addition, when the plurality of data processors are about to simultaneously use stored data for each write request, the data processors must prioritize or matching of data along the time axis must be ensured. That is, when a plurality of write requests are generated, the latest data must always be preferentially overwritten.
A general parallel write control method by a plurality of data processor for a plurality of storage units will be described below by way of some examples.
In one example, counter values xe2x80x9c0xe2x80x9d to xe2x80x9c3xe2x80x9d are described in tables corresponding to identifiers included in the headers of communication cells such as ATM cells. For convenience, one identifier is corresponds to an index for referring to a table. The entity of this table is stored in a main storage unit outside the communication apparatus.
Every time a cell having an identifier which has not been used for internal processing yet is received by the communication apparatus at a predetermined period (a period shorter than a long processing period on the host side), a copy of the data stored in the main storage unit with an index corresponding to the identifier is stored in a storage unit of the communication apparatus and, more specifically, a cache memory. Upon completion of this processing operation of a cell having the same identifier, the content written in the cache memory is rewritten in the main storage unit.
On the host side, a second data processor increments the counter values of the tables corresponding to all indices in the main storage unit by one at a predetermined period (long period). In the communication apparatus, every time a cell is received, a first data processor loads a table corresponding to the identifier from index data in the cache memory and initializes the counter value to xe2x80x9c0xe2x80x9d, thereby updating the data in the main storage unit of the cache memory.
The second data processor independently performs write processing operations in the main storage unit. The first data processor independently performs processing for the cache memory. Therefore, unless stored data having the same index are written in overlapping time periods, matching of these stored data is not degraded by the write processing operations in the main storage unit and the cache memory.
However, the main storage unit and the cache memory have the relationship between an entity (original data) and a duplicate (a copy of the original data). When stored data having the same index are independently written in the main storage unit and the cache memory in overlapping time periods, matching of these stored data may be degraded in a rewrite processing operation of the contents stored in the cache memory in the main storage unit.
Assume that the counter value of the table is xe2x80x9c1xe2x80x9d, and the second data processor increments the counter value to xe2x80x9c2xe2x80x9d. The second data processor refers to the table in the main storage unit that increments the counter value. At this time point, the counter value of the table is still xe2x80x9c1xe2x80x9d. The second data processors loads the counter value xe2x80x9c1xe2x80x9d, increments the counter value by one, and writes xe2x80x9c2xe2x80x9d in the table of the main storage unit.
In some cases, communication cells having identifiers representing the same index are received by the communication apparatus while the second data processors loads the table and rewrites the counter value. If the first data processor has initialized the counter value to xe2x80x9c0xe2x80x9d, the counter value xe2x80x9c2xe2x80x9d rewritten by the second data processor is based on the counter value xe2x80x9c1xe2x80x9d, i.e., the old data before being processed by the first data processor. For this reason, the second data processor overwrites the counter value xe2x80x9c2xe2x80x9d, although the counter value xe2x80x9c1xe2x80x9d obtained by incrementing the initialized counter value xe2x80x9c0xe2x80x9d by one is supposed to be rewritten, thus degrading the matching.
Such mismatching of stored data among the plurality of storage units results from the fact that the data processor for independently performing processing for the storage units cannot perform real-time processing. Therefore, when the stored data are to be processed in parallel in almost overlapping time periods by a plurality of factors, the problem of mismatching cannot be avoided.
Conventionally, to maintain matching of stored data, two or more data processors sequentially perform write processing in the corresponding storage units such that the processing periods of the data processor do not overlap. When a certain data processor is performing a processing operation including a write processing operation in the storage unit in the same processing block, and another independent data processor is to perform a processing operation including a write processing operation in a storage unit in a self processing block, less urgent processing operation must wait until more urgent processing operation has ended.
More specifically, assume that the second data processor for incrementing the counter by one and the first data processor for initializing the counter value to xe2x80x9c0xe2x80x9d are to perform processing of table data corresponding to the same index in overlapping periods. Even when the data processor has already started a series of processing operations from counter value load processing to counter value rewrite processing in the counter, processing operations performed by the second data processor are canceled when the first data processor having a high urgency level generates a request for loading the same index. After the counter value is initialized to xe2x80x9c0xe2x80x9d by the first data processor, the second data processor loads the counter value again, increments the counter value by one, and rewrites the counter value xe2x80x9c1xe2x80x9d.
Two conventional techniques are used to ensure matching of stored data. One is called an updating scheme. When data is written in a particular storage unit that has copied data, data in all the remaining storage units that have copied data and the storage unit with the original data are updated with the rewritten data.
The other technique is called an invalid scheme. When data is written in a particular storage unit that has the copied data, all the remaining storage units and the storage unit with the original data are notified of the address data of this storage area. Using this technique, the system indicates that the data which has already been written in the storage area at the address is not the latest data. Thus, this invalidates the data in the remaining storage units.
In the updating scheme, when one data processor has written data in the storage area of a storage unit in the same processing block, other data processor which are going to write data in the same storage area cancel their processing operations. Processing in the storage unit in the self processing block must be uselessly performed later again from the beginning.
In the invalid scheme as well, if data stored in the storage unit is subjected to a write processing operation or a reference is invalidated, data in the storage area must be read again to perform a processing operation.
In both the above schema, write processing in the same storage area must be sequentially performed.
Conventionally, to protect matching of stored data, when two or more data processor are to write data in the same storage area, processing of each data processor must be sequentially performed.
However, when data stored in the same storage area is to be continuously used for a long period of time by a data processor which has a high priority and has started processing first, a data processor which has a lower priority must therefore perform its processing operation after the processor with the higher priority. In some cases, the data processor with the high priority cannot complete its processing operator within a predetermined time period and the data processor with the lower priority needs to perform a processing operation.
The above-described counter in the communication table will be considered. While cells having the same index are continuously processed through a pipeline, the first data processor continuously performs processing using stored data corresponding to the index. In this case, the second data processor waits for processing. In some cases, the first data processor cannot complete its processing operation within the given time limit before the second data processor must begin its processing operation.
Conventionally, although data written both as original data and copied data, data newly written is not updated and copied.
For example, when the first data processor has written data in the above-described table of the cache memory in which the counter value is stored, the data can be updated in rewriting the stored data from the cache memory side to the main storage unit side. However, in the prior art, data written by the second data processor in the main storage unit is not updated on the cache memory side where the data has already been cached. This causes the following disadvantages.
When cells with the same index data continuously exist at least in the pipeline, stored data which has been loaded once is continuously used without being read from the main storage unit, thereby increasing the cache""s efficiency. Assume that a cache memory holding stored data corresponding to a certain index is continuously used for a long time. Even when the second data processor performs processing operations during this time period, rewriting of the stored data corresponding to the index is not updated on the cache memory side. Therefore, the first data processor performs processing by continuously using old stored data which has not been rewritten by the second data processor.
In a communication control apparatus such as an ATM switching system whose development is in progress, processing associated with a cell is performed using an internal cache memory, and processing for the maintenance/operation of all lines is often performed using a main storage unit. In this situation, if the capacity of the storage area of the cache memory is increased to improve the cache""s efficiency, data for one line may be kept cached for a long time. Assuming that the contents which have been rewritten in the main storage unit are not updated in the already cached stored data, as in the prior art, if line data is frequently used for cell processing, processing for the maintenance/operation of cache lines degrades matching of stored data in the cache memory that performs cell processing.
In addition, assume that when a write processing operation by a plurality of data processor in the same storage area becomes congested and processing is to be sequentially performed. If processing operations for short time periods become congested and a new processing operation for a long time period is created afterwards, the processing operation for the long period must wait. However, both the processing operations for the short time period and the long time period become congested for a long period, and the processing operation for the long period becomes substantially disabled.
Assume that, processing associated with a cell is performed using the internal cache memory, and processing for the maintenance/operation of all lines is performed using the main storage unit. In this case, if a large-scale line is set, the cell arrival frequency of this line becomes high. When a line flow {fraction (1/16)} that of all lines is set for a line A, a cell arrives at the line A every 16-cell period. If processing for the maintenance/operation of all lines takes a time corresponding to the 16-cell period, a cell arrives at the line A at a very high probability for this 16-cell period, so the processing for the maintenance/operation of the line A is substantially disabled. This tendency becomes more conspicuous as the line flow increases, and the processing time for a long period increases. If the total line flow is substantially occupied by one line, maintenance/operation processing of lines is completely disabled.
It is an advantage of the present invention to provide a storage unit control method and apparatus for allowing data processors arranged in parallel for processing stored data to read/write a plurality of stored data without degrading matching among the stored data.
According to the present invention, there is provided a storage means control method comprising the steps of causing first processing means to perform write processing in first storage means, causing tag data control means to manage tag data representing storage areas where the first processing means has performed write processing in the first storage means, causing priority data control means to manage priority data representing a priority of write processing of the first processing means in units of storage areas of second storage means, causing prevention data control means to generate and manage prevention data for preventing write processing in each storage area of the second storage means using the priority data stored in the priority data control means and the tag data managed by the tag data control means, and causing processing data updating means to update the data written in the first storage means on the second storage means on the basis of the prevention data managed by the prevention data control means.
According to the present invention, when different processing means are performing write processing in corresponding storage means in overlapping periods, data with a high priority can be updated on the data stored in the respective storage means. Therefore, the contents of all the storage means can be matched in accordance with the latest data.
This method may further comprise the step of causing second processing means to perform write processing in second storage means. In addition, this method can also be applied even when the processing means and the storage means comprise first to Nth processing means and first to Nth storage means, respectively.
The method may further comprise the steps of changing with time at least one of the tag data managed by the tag data control means or the first, second, . . . , Nth tag data managed by the first, second, . . . , Nth tag data control means and the priority data managed by the priority data control means, and accordingly changing with time the prevention data managed by the prevention data control means.
The step of updating the data stored in the first storage means on the data stored in the second storage means may be performed upon completion of processing by the first processing means. Alternatively, the step of updating the data stored in the second, third, . . . , Nth storage means on the data stored in the first storage means by the processing data updating means may be performed upon completion of write processing in the first storage means by the first processing means, the step of updating the data stored in the first, third, . . . , Nth storage means on the data stored in the second storage means by the processing data updating means may be performed upon completion of write processing in the second storage means by the second processing means, and the step of updating the data stored in the first, second, . . . , (N-th) storage means on the data stored in the Nth storage means by the processing data updating means may be performed upon completion of write processing in the Nth storage means by the Nth processing means.
The method may further comprise the step of causing the tag data control means to accumulate and manage the first, second, . . . , Nth tag data obtained when the first, second, . . . , Nth processing means perform processing in the first, second, . . . , Nth storage means excluding Jth storage means, respectively, before Jth processing means of the first, second, . . . , Nth processing means completes processing in the Jth storage means.
According to the present invention, there is also provided a storage means control apparatus comprising first write processing means for performing write processing in first storage means, tag data control means for managing tag data representing storage areas where the first write processing means has performed write processing in the first storage means, priority data control means for managing priority data representing a priority of write processing of the first write processing means in units of storage areas of second storage means, prevention data control means for generating and managing prevention data for preventing write processing in each storage area of the second storage means using the priority data managed by the priority data control means and the tag data managed by the tag data control means, and processing data updating means for writing the data written in the first storage means in the second storage means on the basis of the prevention data managed by the prevention data control means.
This arrangement can also be applied even when the processing means and the storage means comprise first to Nth processing means and first to Nth storage means, respectively.
The apparatus may further comprise means for changing with time at least one of the tag data managed by the tag data control means or the first, second, . . . , Nth tag data managed by the first, second, . . . , Nth tag data control means and the priority data managed by the priority data control means. The prevention data managed by the prevention data control means may be accordingly changed with time, and the prevention data may be changed along with a progress in processing by the processing means.
Processing of updating the data stored in the first storage means on the data stored in the second storage means may be performed upon completion of processing by the first processing means. Alternatively, the processing data updating means may perform processing of updating the data stored in the second, third, . . . , Nth storage means on the data stored in the first storage means upon completion of write processing in the first storage means by the first processing means, processing of updating the data stored in the first, third, . . . , Nth storage means on the data stored in the second storage means upon completion of write processing in the second storage means by the second processing means, and processing of updating the data stored in the first, second, . . . , (N-th) storage means on the data stored in the Nth storage means upon completion of write processing in the Nth storage means by the Nth processing means.
The tag data control means may accumulate and manage the first, second, . . . , Nth tag data obtained when the first, second, . . . , Nth processing means perform processing in the first, second, . . . , Nth storage means excluding Jth storage means, respectively, before Jth processing means of the first, second, . . . , Nth processing means completes processing in the Jth storage means.